package sort;

import java.util.Arrays;

public class quickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low >= high) {
            return; // 递归终止条件：子数组长度小于等于1
        }
        int left = low;
        int right = high;
        int pivot = arr[low]; // 基准值

        while (left < right) {
            // 从右向左找小于pivot的数
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            if (left < right) {
                arr[left] = arr[right]; // 填左坑，形成新右坑
            }

            // 从左向右找大于pivot的数
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            if (left < right) {
                arr[right] = arr[left]; // 填右坑，形成新左坑
                right--;
            }
        }
        arr[left] = pivot; // 将pivot放入最终坑位

        // 递归排序左右子数组
        quickSort(arr, low, left - 1);
        quickSort(arr, left + 1, high);
    }
    public static void main(String[] args) {
        int[] a = new int[]{22,13,3,44,24};
        quickSort(a,0, a.length-1);
        System.out.println(Arrays.toString(a));
    }
}
